Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

Q is empty.


QTRS
  ↳ Overlay + Local Confluence

Q restricted rewrite system:
The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

Q is empty.

The TRS is overlay and locally confluent. By [19] we can switch to innermost.

↳ QTRS
  ↳ Overlay + Local Confluence
QTRS
      ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)


Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) → DIN(der(X))
U41(dout(DX), X) → U42(din(der(DX)), X, DX)
DIN(der(der(X))) → U41(din(der(X)), X)
U31(dout(DX), X, Y) → U32(din(der(Y)), X, Y, DX)
U21(dout(DX), X, Y) → U22(din(der(Y)), X, Y, DX)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))
U31(dout(DX), X, Y) → DIN(der(Y))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.

↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
QDP
          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) → DIN(der(X))
U41(dout(DX), X) → U42(din(der(DX)), X, DX)
DIN(der(der(X))) → U41(din(der(X)), X)
U31(dout(DX), X, Y) → U32(din(der(Y)), X, Y, DX)
U21(dout(DX), X, Y) → U22(din(der(Y)), X, Y, DX)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))
U31(dout(DX), X, Y) → DIN(der(Y))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 3 less nodes.

↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
QDP
              ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → DIN(der(X))
U31(dout(DX), X, Y) → DIN(der(Y))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].


The following pairs can be oriented strictly and are deleted.


U31(dout(DX), X, Y) → DIN(der(Y))
The remaining pairs can at least be oriented weakly.

DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(der(X))) → DIN(der(X))
Used ordering: Polynomial interpretation [25]:

POL(DIN(x1)) = 0   
POL(U21(x1, x2, x3)) = 0   
POL(U31(x1, x2, x3)) = x1   
POL(U41(x1, x2)) = 0   
POL(der(x1)) = 0   
POL(din(x1)) = 0   
POL(dout(x1)) = 1 + x1   
POL(plus(x1, x2)) = 0   
POL(times(x1, x2)) = 0   
POL(u21(x1, x2, x3)) = x1   
POL(u22(x1, x2, x3, x4)) = 1 + x1 + x4   
POL(u31(x1, x2, x3)) = x1   
POL(u32(x1, x2, x3, x4)) = 1 + x4   
POL(u41(x1, x2)) = x1   
POL(u42(x1, x2, x3)) = x1   

The following usable rules [17] were oriented:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u42(dout(DDX), X, DX) → dout(DDX)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
din(der(der(X))) → u41(din(der(X)), X)



↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
QDP
                  ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → U31(din(der(X)), X, Y)
DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.

↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
QDP
                      ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
U21(dout(DX), X, Y) → DIN(der(Y))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].


The following pairs can be oriented strictly and are deleted.


U21(dout(DX), X, Y) → DIN(der(Y))
The remaining pairs can at least be oriented weakly.

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))
Used ordering: Polynomial interpretation with max and min functions [25]:

POL(DIN(x1)) = 0   
POL(U21(x1, x2, x3)) = x1   
POL(U41(x1, x2)) = 0   
POL(der(x1)) = 0   
POL(din(x1)) = 0   
POL(dout(x1)) = 1 + x1   
POL(plus(x1, x2)) = 0   
POL(times(x1, x2)) = 0   
POL(u21(x1, x2, x3)) = x1   
POL(u22(x1, x2, x3, x4)) = x1   
POL(u31(x1, x2, x3)) = x1   
POL(u32(x1, x2, x3, x4)) = 1 + x4   
POL(u41(x1, x2)) = x1   
POL(u42(x1, x2, x3)) = 1 + x1   

The following usable rules [17] were oriented:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u42(dout(DDX), X, DX) → dout(DDX)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
din(der(der(X))) → u41(din(der(X)), X)



↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
QDP
                          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → U21(din(der(X)), X, Y)
DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.

↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
                        ↳ QDP
                          ↳ DependencyGraphProof
QDP
                              ↳ QDPOrderProof
                              ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].


The following pairs can be oriented strictly and are deleted.


U41(dout(DX), X) → DIN(der(DX))
The remaining pairs can at least be oriented weakly.

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))
Used ordering: Polynomial interpretation with max and min functions [25]:

POL(DIN(x1)) = 0   
POL(U41(x1, x2)) = x1   
POL(der(x1)) = 0   
POL(din(x1)) = 0   
POL(dout(x1)) = 1   
POL(plus(x1, x2)) = 0   
POL(times(x1, x2)) = 0   
POL(u21(x1, x2, x3)) = x1   
POL(u22(x1, x2, x3, x4)) = 1 + x1   
POL(u31(x1, x2, x3)) = x1   
POL(u32(x1, x2, x3, x4)) = 1 + x1   
POL(u41(x1, x2)) = x1   
POL(u42(x1, x2, x3)) = 1   

The following usable rules [17] were oriented:

u42(dout(DDX), X, DX) → dout(DDX)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
din(der(der(X))) → u41(din(der(X)), X)
din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)



↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
                        ↳ QDP
                          ↳ DependencyGraphProof
                            ↳ QDP
                              ↳ QDPOrderProof
QDP
                                  ↳ DependencyGraphProof
                              ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(der(X))) → U41(din(der(X)), X)
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 1 less node.

↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
                        ↳ QDP
                          ↳ DependencyGraphProof
                            ↳ QDP
                              ↳ QDPOrderProof
                                ↳ QDP
                                  ↳ DependencyGraphProof
QDP
                                      ↳ UsableRulesProof
                              ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
                        ↳ QDP
                          ↳ DependencyGraphProof
                            ↳ QDP
                              ↳ QDPOrderProof
                                ↳ QDP
                                  ↳ DependencyGraphProof
                                    ↳ QDP
                                      ↳ UsableRulesProof
QDP
                                          ↳ QReductionProof
                              ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))

R is empty.
The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)



↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
                        ↳ QDP
                          ↳ DependencyGraphProof
                            ↳ QDP
                              ↳ QDPOrderProof
                                ↳ QDP
                                  ↳ DependencyGraphProof
                                    ↳ QDP
                                      ↳ UsableRulesProof
                                        ↳ QDP
                                          ↳ QReductionProof
QDP
                                              ↳ UsableRulesReductionPairsProof
                              ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the usable rules with reduction pair processor [15] with a polynomial ordering [25], all dependency pairs and the corresponding usable rules [17] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

DIN(der(times(X, Y))) → DIN(der(X))
DIN(der(plus(X, Y))) → DIN(der(X))
No rules are removed from R.

Used ordering: POLO with Polynomial interpretation [25]:

POL(DIN(x1)) = 2·x1   
POL(der(x1)) = 2·x1   
POL(plus(x1, x2)) = 2·x1 + x2   
POL(times(x1, x2)) = 2·x1 + x2   



↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
                        ↳ QDP
                          ↳ DependencyGraphProof
                            ↳ QDP
                              ↳ QDPOrderProof
                                ↳ QDP
                                  ↳ DependencyGraphProof
                                    ↳ QDP
                                      ↳ UsableRulesProof
                                        ↳ QDP
                                          ↳ QReductionProof
                                            ↳ QDP
                                              ↳ UsableRulesReductionPairsProof
QDP
                                                  ↳ QDPSizeChangeProof
                              ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

DIN(der(der(X))) → DIN(der(X))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:


We use the reduction pair processor [15].


The following pairs can be oriented strictly and are deleted.


DIN(der(der(X))) → U41(din(der(X)), X)
The remaining pairs can at least be oriented weakly.

DIN(der(times(X, Y))) → DIN(der(X))
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))
Used ordering: Polynomial interpretation [25]:

POL(DIN(x1)) = 1   
POL(U41(x1, x2)) = x1   
POL(der(x1)) = 0   
POL(din(x1)) = 0   
POL(dout(x1)) = 1   
POL(plus(x1, x2)) = 0   
POL(times(x1, x2)) = 0   
POL(u21(x1, x2, x3)) = x1   
POL(u22(x1, x2, x3, x4)) = 1 + x1   
POL(u31(x1, x2, x3)) = x1   
POL(u32(x1, x2, x3, x4)) = 1 + x1   
POL(u41(x1, x2)) = x1   
POL(u42(x1, x2, x3)) = 1 + x1   

The following usable rules [17] were oriented:

u42(dout(DDX), X, DX) → dout(DDX)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
din(der(der(X))) → u41(din(der(X)), X)
din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)



↳ QTRS
  ↳ Overlay + Local Confluence
    ↳ QTRS
      ↳ DependencyPairsProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ QDP
              ↳ QDPOrderProof
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ QDP
                      ↳ QDPOrderProof
                        ↳ QDP
                          ↳ DependencyGraphProof
                            ↳ QDP
                              ↳ QDPOrderProof
                              ↳ QDPOrderProof
QDP

Q DP problem:
The TRS P consists of the following rules:

DIN(der(times(X, Y))) → DIN(der(X))
U41(dout(DX), X) → DIN(der(DX))
DIN(der(plus(X, Y))) → DIN(der(X))
DIN(der(der(X))) → DIN(der(X))

The TRS R consists of the following rules:

din(der(plus(X, Y))) → u21(din(der(X)), X, Y)
u21(dout(DX), X, Y) → u22(din(der(Y)), X, Y, DX)
u22(dout(DY), X, Y, DX) → dout(plus(DX, DY))
din(der(times(X, Y))) → u31(din(der(X)), X, Y)
u31(dout(DX), X, Y) → u32(din(der(Y)), X, Y, DX)
u32(dout(DY), X, Y, DX) → dout(plus(times(X, DY), times(Y, DX)))
din(der(der(X))) → u41(din(der(X)), X)
u41(dout(DX), X) → u42(din(der(DX)), X, DX)
u42(dout(DDX), X, DX) → dout(DDX)

The set Q consists of the following terms:

din(der(plus(x0, x1)))
u21(dout(x0), x1, x2)
u22(dout(x0), x1, x2, x3)
din(der(times(x0, x1)))
u31(dout(x0), x1, x2)
u32(dout(x0), x1, x2, x3)
din(der(der(x0)))
u41(dout(x0), x1)
u42(dout(x0), x1, x2)

We have to consider all minimal (P,Q,R)-chains.